﻿#include<stdio.h>
#define GNUM 10
#define GLEN 10

/*
  Name: 语法分析程序 
  Copyright: 2011
  Author: 杨晓辰 
  Date: 24/04/11 11:23
  Description: 根据LL(1)语法句子产生first集,follow集,预测分析表,然后读入句子进行分析. 
*/


int gnum,nnum,tnum; // 分别为句子数,非终结符数,终结符. 
char nset[GNUM]; // 存放非终结符的数组, 下面没有用到... 
char tset[GNUM]; // 存放终结符的数组 

typedef struct{             // 结构体 G 代表一个句子  下面以 E->DT|@ 为例 
    char n;  // 句首非终结符 例: E 
    
    int s_num; // 候选式数量 例: 2 
    int s_len[GLEN]; // 每个候选式长度 例: 2,1 
    char s[GNUM][GLEN]; // 存放候选式 {D,T},{@} 
    
    int fi_len; // first集元素数量  
    char first[GNUM]; // 句首非终结符的first集:  First(E) 
    
    int fo_len; //follow集元素数量 
    char follow[GNUM]; // follow(E) 
}G;
G g[GNUM]; // 句子数组 

int table[GNUM][GNUM]; // 存放分析表 

char s[2*GNUM]; // 存放需要分析的字符串 


/*
  打印一个句字的信息，包括这个句子句首非终结符的first集和follow集。 
*/
void printfG(G g){ 
    int i,j;
    printf("%c -> ",g.n);
    for(i=0;i<g.s_num;i++){
        for(j=0;j<g.s_len[i];j++){
            printf("%c",g.s[i][j]);
        }
        printf("|");
    }
    printf("\nfirst = ");
    for(i=0;i<g.fi_len;i++){
        printf("%c ",g.first[i]);
    }
    printf("\nfollow = ");
    for(i=0;i<g.fo_len;i++){
        printf("%c ",g.follow[i]);
    }
    printf("\n\n");
}

/*
  读取语法文件。 
*/
int readG(){
    int i,j,k;
    char ch;
    FILE *fp;
    if((fp=fopen("g.txt","r"))==NULL){
        printf("Can't open file \"g.txt\"!\n");
        system("pause");
        exit(0);
    }   
    fscanf(fp,"%d %d %d",&nnum,&tnum,&gnum);
    printf("%d %d %d\n",gnum,nnum,tnum);
    fgetc(fp);
    for(i=0;i<nnum;i++){
        nset[i]=fgetc(fp);
    }
    fgetc(fp);
    for(i=0;i<tnum;i++){
        tset[i]=fgetc(fp);
    }
    fgetc(fp);
    for(i=0;i<gnum;i++){
        g[i].n=fgetc(fp);
        
        g[i].fi_len=0;
        g[i].fo_len=0;
     
        fgetc(fp);
        fgetc(fp);
        j=0;
        g[i].s_len[j]=0;
        g[i].s_num=1;
        
        while((ch=fgetc(fp))!='\n' && !feof(fp)){
            
            if(ch=='|'){
                j++;
                g[i].s_len[j]=0;
                g[i].s_num++;
                continue;
            }else {
                g[i].s[j][g[i].s_len[j]++]=ch;
            }
        }       
        //printfG(g[i]); 
    }
    system("pause");   
    fclose(fp);
}


/*
    找到以参数字符 n 作为句首非终结符的句子，
    找到的话，返回其在数组中的下标，
    如果没找到，返回-1. 
*/
int findN(char n){
    int i;
    for(i=0;i<nnum;i++){
        if(g[i].n==n){
            return i;
        }
    }
    return -1;
}

/*
    找到以参数字符 t 在终结符数组中的位置，
    找到的话，返回其在数组中的下标，
    如果没找到，返回-1. 
*/
int findT(char t){
    int i;
    for(i=0;i<tnum;i++){
        if(tset[i]==t){
            return i;
        }
    }
    return -1;
}

/*
    找到以参数字符 n 在句子 g 里句首非终结符的first集里的位置，
    找到的话，返回其在数组中的下标，
    如果没找到，返回-1. 
*/
int findInFirst(G g,char n){
    int i;
    for(i=0;i<g.fi_len;i++){
        if(g.first[i]==n){
            return i;
        }
    }
    return -1;
}

/*
    找到以参数字符 n 在句子 g 里句首非终结符的follow集里的位置，
    找到的话，返回其在数组中的下标，
    如果没找到，返回-1. 
*/
int findInFollow(G g,char n){
    int i;
    for(i=0;i<g.fo_len;i++){
        if(g.follow[i]==n){
            return i;
        }
    }
    return -1;
}

/*
    将sg中的first集或follow集元素，加入dg中的集合，并保证不重复。 
    type=0，sg.first/空字 加入到 dg.first
    type=1, sg.follow/空字 加入到 dg.follow
    type=2, sg.first/空字 加入到 dg.follow 
*/
void joinSet(G *dg,G sg,int type){
    int i,j,flag;
    if(type==0){
        for(i=0;i<sg.fi_len;i++){
            if(sg.first[i]=='@'){
                continue;
            }
            flag=0;
            for(j=0;j<dg->fi_len;j++){
                if(sg.first[i]==dg->first[j]){
                    flag=1;
                    break;
                }
            }
            if(flag==0){
                dg->first[dg->fi_len]=sg.first[i];
                (dg->fi_len)++;
            }
        }
    }else if(type==1){
        for(i=0;i<sg.fo_len;i++){
            if(sg.follow[i]=='@'){
                continue;
            }
            flag=0;
            for(j=0;j<dg->fo_len;j++){
                if(sg.follow[i]==dg->follow[j]){
                    flag=1;
                    break;
                }
            }
            if(flag==0){
                dg->follow[dg->fo_len]=sg.follow[i];
                (dg->fo_len)++;
            }
        }
    }else {
        for(i=0;i<sg.fi_len;i++){
            if(sg.first[i]=='@'){
                continue;
            }
            flag=0;
            for(j=0;j<dg->fo_len;j++){
                if(sg.first[i]==dg->follow[j]){
                    flag=1;
                    break;
                }
            }
            if(flag==0){
                dg->follow[dg->fo_len]=sg.first[i];
                (dg->fo_len)++;
            }
        }
    }
}


/*
    将字符 ch ，加入dg中的集合,如果有,则不加. 
    type=0，ch 加入到 dg.first
    type=1, ch 加入到 dg.follow
*/
void joinChar(G *dg,char ch,int type){
    int i,j,flag=0;
    if(type==0){
        for(i=0;i<dg->fi_len;i++){
            if(dg->first[i]==ch){
                flag=1;
                break;
            }
        }
        if(flag==0){
            dg->first[dg->fi_len]=ch;
            (dg->fi_len)++;
        }
    }else {
        for(i=0;i<dg->fo_len;i++){
            if(dg->follow[i]==ch){
                flag=1;
                break;
            }
        }
        if(flag==0){
            dg->follow[dg->fo_len]=ch;
            (dg->fo_len)++;
        }
    }
}


/*
    判断first（n）中是否含有空字。有则返回1，没有返回0。 
*/
int hasBlank(char n){
    int i,temp;
    temp=findN(n);
    for(i=0;i<g[temp].fi_len;i++){
        if(g[temp].first[i]=='@'){
            return 1;
        }
    }
    return 0;
}

/*
    求出所有非终结符的first集 
*/
void getFirst(){
    int oldlen[GNUM]={0};
    int i,j,k,flag=1;
    int temp;
    
    while(flag){
        for(i=0;i<gnum;i++){
            for(j=0;j<g[i].s_num;j++){
                if((temp=findT(g[i].s[j][0]))!=-1){
                    joinChar(&g[i],g[i].s[j][0],0);
                }else if(g[i].s[j][0]=='@'){
                    joinChar(&g[i],'@',0);
                }else {
                    temp=findN(g[i].s[j][0]);
                    joinSet(&g[i],g[temp],0);
                    for(k=0;k<g[i].s_len[j]-1;k++){
                        if((temp=findN(g[i].s[j][k]))!=-1 && hasBlank(g[i].s[j][k])){ //如果字符是非终结符且含有空字,一旦有终结符,或者非终结符不含空字,结束循环 
                            if((temp=findT(g[i].s[j][k+1]))!=-1){         // 如果下一个字符是终结符,将此终结符加入first集 
                                joinChar(&g[i],g[i].s[j][k+1],0);
                                break; 
                            }else {  //如果是非终结符,将其first集加入 
                                temp=findN(g[i].s[j][k+1]);
                                joinSet(&g[i],g[temp],0);
                            } 
                        }else {
                            break; 
                        } 
                    }
                    if(k==g[i].s_len[j]){ //如果前面字符全都是非终结符,且均含有空字,且最后一个字符也是非终结符. 
                        if(hasBlank(g[i].s[j][k])){ //且最后一个非终结符的first集中也有空字. 
                            joinChar(&g[i],'@',0);
                        }
                    }
                }              
            }
        }
        
        // 判断各first集是否在增大       
        flag=0;
        for(i=0;i<gnum;i++){
            if(oldlen[i]<g[i].fi_len){
                for(j=i;j<gnum;j++){
                    oldlen[i]=g[i].fi_len;
                }
                flag=1;
                break;
            }
        }
    }  
}

/*
    求出所有非终结符的follow集 
*/
void getFollow(){
    int oldlen[GNUM]={0};
    int i,j,k,q,flag=1,temp,temp_next;
    g[0].follow[0]='#';
    g[0].fo_len++;  
    while(flag){
        for(i=0;i<gnum;i++){
            for(j=0;j<g[i].s_num;j++){
                for(k=g[i].s_len[j]-1;k>=0;k--){
                    if((temp=findT(g[i].s[j][k]))!=-1){
                        continue;
                    }else if((temp=findN(g[i].s[j][k]))!=-1){ //当前字符是非终结符,则要求其follow集 
                        if(k==g[i].s_len[j]-1){
                            joinSet(&g[temp],g[i],1);
                        }else{
                            for(q=k+1;q<g[i].s_len[j];q++){
                                if((temp_next=findT(g[i].s[j][k+1]))!=-1){ //如果紧跟着的是终结符,加入follow集退出循环. 
                                    joinChar(&g[temp],g[i].s[j][k+1],1);
                                    break;
                                    
                                }else { //如果跟着的是非终结符.
                                    temp_next=findN(g[i].s[j][q]);   // 先将后续第一个字符first集加入当前字符follow集 
                                    joinSet(&g[temp],g[temp_next],2); // 实现上一行作用 
                                    
                                    if(hasBlank(g[i].s[j][q])){ // 如果后续字符first集中有空字 
                                        if(q+1<g[i].s_len[j]){ //后面还有字符 
                                            continue; 
                                        }else{ //当后面没有字符时,说明当前k位置字符之后的first集存在空字. 
                                            joinSet(&g[temp],g[i],1);
                                        } 
                                    }else { // 当紧跟着的终结符first集中没有空字,退出循环 
                                        break;
                                    }
                                    
                                    
                                }
                                
                            }
                        }
                    }
                }
            }
        }
        // 判断各follow集是否在增大 
        flag=0;
        for(i=0;i<gnum;i++){
            if(oldlen[i]<g[i].fo_len){
                for(j=i;j<gnum;j++){
                    oldlen[i]=g[i].fo_len;
                }
                flag=1;
                break;
            }
        }
    }

}

/*
    构造预测分析表. 
*/
void createAnalysisTable(){
    int i,j,k,q,temp;
    
    for(i=0;i<nnum;i++){
        for(j=0;j<tnum;j++){
            table[i][j]=-1;
        }  
    }
    
    for(i=0;i<gnum;i++){
        for(j=0;j<g[i].s_num;j++){
            for(q=0;q<tnum;q++){ // 为每个终结符tset(q)寻找产生式. 
                for(k=0;k<g[i].s_len[j];k++){  // 在产生式的first集中找终结符tset(q). 
                                                                              
                    if((temp=findT(g[i].s[j][k]))!=-1){
                        if(g[i].s[j][k]==tset[q]){
                            table[i][q]=j;
                        }
                        break; 
                    
                    }else if((temp=findN(g[i].s[j][k]))!=-1){
                        if(findInFirst(g[temp],tset[q])!=-1){ // 如果在产生式的first集中 
                            table[i][q]=j;
                            if(findInFirst(g[temp],'@')!=-1){ // 如果此非终结符first集中有空字.则可以循环检查下一个字符. 
                                continue;
                            }else {
                                break;
                            }
                        }else { // 如果不在 
                            if(findInFirst(g[temp],'@')!=-1){ // 如果此非终结符first集中有空字.则可以循环检查下一个字符. 
                                continue;
                            }else {
                                break;
                            }
                        }
                    }else {
                        k=g[i].s_len[j];
                        break;
                    }                    
                }
                
                if(k==g[i].s_len[j]){ //这说明检查了这个产生式的每个字符,均为非终结符且first集有空字. 
                    for(k=0;k<g[i].fo_len;k++){
                        table[i][findT(g[i].follow[k])]=j;
                    }
                }
            }
        }
    }
}

/*
    读取需要分析的字符串 
*/ 
void readSentence(){
    FILE *fp;
    int i=0;
    if((fp=fopen("sentence.txt","r"))==NULL){
        printf("Can't open the file \"sentence.txt\"!\n");
        system("pause");
        exit(0);
    }
    while(!feof(fp)){
        s[i++]=fgetc(fp);
        if(s[i-1]=='#'){
            break;
        }
    } 
}

/*
    分析错误的打印函数 
*/
void printError(int i){
    printf("!!!There is a error at index %d!\n",i);
}

/*
    对字符串进行分析.如果有错误将会执行错误打印函数.正确则不进行打印. 
*/
void analyse(){
    char stack[2*GNUM];
    int top=0;
    int i=0,j,k,p,q;
    int flag=1;
    char x;
    
    stack[top++]='#';
    stack[top++]=g[0].n;
    
    while(flag){
        
        for(p=0;p<top;p++){
            printf("%c",stack[p]);
        }
        printf("\t\ti=%d\n",i);
        
        x=stack[--top];
        if(findT(x)!=-1 && x!='#'){
            if(x==s[i]){
                i++;
            }else{
                printError(i);
                break;
            }
        }else if(x=='#'){
            if(x==s[i]){
                flag=0;
            }else{
                printError(i);
                break;
            }
        }else if((j=table[findN(x)][findT(s[i])])!=-1){
            p=findN(x);
            if(g[p].s[j][0]!='@'){
                for(k=g[p].s_len[j]-1;k>=0;k--){
                    stack[top++]=g[p].s[j][k];
                }
            }
        }else {
            printError(i);
            break;
        }
    }
    printf("Analyse Complete!\n");
}


/*
    主控制函数 
*/ 
int main(){
    int i,j;
    readG();
    getFirst();
    getFollow();
    createAnalysisTable();
    readSentence();
    
    // 打印所有句子和各非终结符的first集,follow集 
    for(i=0;i<gnum;i++){
        printfG(g[i]);
    }
    
    // 打印预测分析表 
    for(i=0;i<nnum;i++){
        for(j=0;j<tnum;j++){
            printf("%d\t",table[i][j]);
        }
        printf("\n\n");    
    }
    
    analyse();
      
    system("pause");
}
